package com.sicheng.lc.周赛.分类.dp.状压;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/12 18:45
 */
public class 分饼干 {
    //    https://leetcode.cn/problems/fair-distribution-of-cookies/
    public static void main(String[] args) {
        分饼干 solution = new 分饼干();
        int[] cookies = {6, 1, 3, 2, 2, 4, 1, 2};
        int k = 3;
        System.out.println(solution.distributeCookies(cookies, k));
    }

    int[] sum;
    int k;
    int max = (int) 1e9;

    public int distributeCookies(int[] cookies, int k) {
        return stateDp(cookies, k);
    }

    public int stateDp(int[] cookies, int k) {
        int n = cookies.length;
        // cookies的所有状态
        int[] sum = new int[1 << n];
        for (int i = 0; i < sum.length; i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1)
                    sum[i] += cookies[j];
            }
        }

        //dp[i,j] 表示划分i组 ,状态为j 的最小不公平度
        int[] dp = new int[1 << n];
        System.arraycopy(sum, 0, dp, 0, sum.length);
        for (int i = 2; i <= k; i++) {
            for (int j = (1 << n) - 1; j >= 0; j--) {
                for (int s = j; s > 0; s = (s - 1) & j) {
                    dp[j] = Math.min(dp[j], Math.max(dp[j ^ s], sum[s]));
                }
            }
        }
        return dp[(1 << n) - 1];
    }


    private void dfs(int[] cookies, int k) {
        this.k = k;
        sum = new int[k];
        dfs(0, cookies);
    }

    private void dfs(int u, int[] cookies) {

        if (u == cookies.length) {
            int max = 0;
            for (int j : sum) {
                max = Math.max(max, j);
            }
            this.max = Math.min(this.max, max);
            return;
        }

        for (int i = 0; i < k; i++) {
            if (sum[i] > max)
                continue;
            sum[i] += cookies[u];
            dfs(u + 1, cookies);
            sum[i] -= cookies[u];
        }
    }
}
